home *** CD-ROM | disk | FTP | other *** search
/ QRZ! Ham Radio 8 / QRZ Ham Radio Callsign Database - Volume 8.iso / mac / files / t_sys5 / unixcpio.gz / unixnet.cpio / iproute.c < prev    next >
C/C++ Source or Header  |  1994-07-11  |  15KB  |  635 lines
  1. /* Lower half of IP, consisting of gateway routines
  2.  * Includes routing and options processing code
  3.  */
  4. #include "global.h"
  5. #include "mbuf.h"
  6. #include "internet.h"
  7. #include "timer.h"
  8. #include "netuser.h"
  9. #include "ip.h"
  10. #include "icmp.h"
  11. #include "iface.h"
  12. #include "trace.h"
  13. #ifdef    UNIX
  14. #include <memory.h>
  15. #endif
  16.  
  17. struct route *routes[32][NROUTE];    /* Routing table */
  18. struct route r_default;            /* Default route entry */
  19.  
  20. int32 ip_addr;
  21. struct ip_stats ip_stats;
  22.  
  23. #ifndef    GWONLY
  24. struct mbuf *loopq;    /* Queue for loopback packets */
  25. #endif
  26.  
  27. /* Route an IP datagram. This is the "hopper" through which all IP datagrams,
  28.  * coming or going, must pass.
  29.  *
  30.  * "rxbroadcast" is set to indicate that the packet came in on a subnet
  31.  * broadcast. The router will kick the packet upstairs regardless of the
  32.  * IP destination address.
  33.  */
  34. int
  35. ip_route(bp,rxbroadcast)
  36. struct mbuf *bp;
  37. char rxbroadcast;    /* True if packet had link broadcast address */
  38. {
  39.     struct mbuf *htonip();
  40.     void ip_recv();
  41.     struct ip ip;            /* IP header being processed */
  42.     int16 ip_len;            /* IP header length */
  43.     int16 length;            /* Length of data portion */
  44.     int32 gateway;            /* Gateway IP address */
  45.     register struct route *rp;    /* Route table entry */
  46.     struct interface *iface;    /* Output interface, possibly forwarded */
  47.     struct route *rt_lookup();
  48.     int16 offset;            /* Offset into current fragment */
  49.     int16 mf_flag;            /* Original datagram MF flag */
  50.     int strict = 0;            /* Strict source routing flag */
  51.     char precedence;        /* Extracted from tos field */
  52.     char delay;
  53.     char throughput;
  54.     char reliability;
  55.     int16 opt_len;        /* Length of current option */
  56.     char *opt;        /* -> beginning of current option */
  57.     char *ptr;        /* -> pointer field in source route fields */
  58.     struct mbuf *tbp;
  59.  
  60.     ip_stats.total++;
  61.     if(len_mbuf(bp) < IPLEN){
  62.         /* The packet is shorter than a legal IP header */
  63.         ip_stats.runt++;
  64.         free_p(bp);
  65.         return -1;
  66.     }
  67.     /* Sneak a peek at the IP header's IHL field to find its length */
  68.     ip_len = (bp->data[0] & 0xf) << 2;
  69.     if(ip_len < IPLEN){
  70.         /* The IP header length field is too small */
  71.         ip_stats.length++;
  72.         free_p(bp);
  73.         return -1;
  74.     }
  75.     if(cksum(NULLHEADER,bp,ip_len) != 0){
  76.         /* Bad IP header checksum; discard */
  77.         ip_stats.checksum++;
  78.         free_p(bp);
  79.         return -1;
  80.     }
  81.     /* Extract IP header */
  82.     ntohip(&ip,&bp);
  83.  
  84.     if(ip.version != IPVERSION){
  85.         /* We can't handle this version of IP */
  86.         ip_stats.version++;
  87.         free_p(bp);
  88.         return -1;
  89.     }
  90.     /* Trim data segment if necessary. */
  91.     length = ip.length - ip_len;    /* Length of data portion */
  92.     trim_mbuf(&bp,length);    
  93.                 
  94.     /* Process options, if any. Also compute length of secondary IP
  95.      * header in case fragmentation is needed later
  96.      */
  97.     strict = 0;
  98.     for(opt = ip.options; opt < &ip.options[ip.optlen];opt += opt_len){
  99.         int32 get32();
  100.  
  101.         /* Most options have a length field. If this is a EOL or NOOP,
  102.          * this (garbage) value won't be used
  103.          */
  104.         opt_len = uchar(opt[1]);
  105.  
  106.         switch(opt[0] & OPT_NUMBER){
  107.         case IP_EOL:
  108.             goto no_opt;    /* End of options list, we're done */
  109.         case IP_NOOP:
  110.             opt_len = 1;
  111.             break;        /* No operation, skip to next option */
  112.         case IP_SSROUTE:    /* Strict source route & record route */
  113.             strict = 1;    /* note fall-thru */
  114.         case IP_LSROUTE:    /* Loose source route & record route */
  115.             /* Source routes are ignored unless we're in the
  116.              * destination field
  117.              */
  118.             if(ip.dest != ip_addr)
  119.                 break;    /* Skip to next option */
  120.             if(uchar(opt[2]) >= opt_len){
  121.                 break;    /* Route exhausted; it's for us */
  122.             }
  123.             /* Put address for next hop into destination field,
  124.              * put our address into the route field, and bump
  125.              * the pointer
  126.              */
  127.             ptr = opt + uchar(opt[2]) - 1;
  128.             ip.dest = get32(ptr);
  129.             put32(ptr,ip_addr);
  130.             opt[2] += 4;
  131.             break;
  132.         case IP_RROUTE:    /* Record route */
  133.             if(uchar(opt[2]) >= opt_len){
  134.                 /* Route area exhausted; kick back an error */
  135.                 union icmp_args icmp_args;
  136.  
  137.                 icmp_args.pointer = IPLEN + opt - ip.options;
  138.                 icmp_output(&ip,bp,PARAM_PROB,0,&icmp_args);
  139.                 free_p(bp);
  140.                 return -1;
  141.             }
  142.             /* Add our address to the route */
  143.             ptr = opt + uchar(opt[2]) - 1;
  144.             ptr = put32(ptr,ip_addr);
  145.             opt[2] += 4;
  146.             break;
  147.         }
  148.     }
  149. no_opt:
  150.  
  151.     /* See if it's a broadcast or addressed to us, and kick it upstairs */
  152.     if(ip.dest == ip_addr || rxbroadcast){
  153. #ifdef    GWONLY
  154.     /* We're only a gateway, we have no host level protocols */
  155.         if(!rxbroadcast)
  156.             icmp_output(&ip,bp,DEST_UNREACH,PROT_UNREACH,(union icmp_args *)NULL);
  157.         free_p(bp);
  158. #else
  159.  
  160.         /* If this is a local loopback packet, place on the loopback
  161.          * queue for processing in the main loop. This prevents the
  162.          * infinite stack recursion and other problems that would
  163.          * otherwise occur when we talk to ourselves, e.g., with ftp
  164.          */
  165.         if(ip.source == ip_addr){
  166.             /* Put IP header back on */
  167.             if((tbp = htonip(&ip,bp)) == NULLBUF){
  168.                 free_p(bp);
  169.                 return -1;
  170.             }
  171.             /* Copy loopback packet into new buffer.
  172.              * This avoids an obscure problem with TCP which
  173.              * dups its outgoing data before transmission and
  174.              * then frees it when an ack comes, even though the
  175.              * receiver might not have actually read it yet
  176.              */
  177.             bp = copy_p(tbp,len_mbuf(tbp));
  178.             free_p(tbp);
  179.             if(bp == NULLBUF)
  180.                 return -1;
  181.             enqueue(&loopq,bp);
  182.         } else {
  183.             ip_recv(&ip,bp,rxbroadcast);
  184.         }
  185. #endif
  186.         return 0;
  187.     }
  188.  
  189.     /* Decrement TTL and discard if zero */
  190.     if(--ip.ttl == 0){
  191.         /* Send ICMP "Time Exceeded" message */
  192.         icmp_output(&ip,bp,TIME_EXCEED,0,NULLICMP);
  193.         free_p(bp);
  194.         return -1;
  195.     }
  196.     /* Look up target address in routing table */
  197.     if((rp = rt_lookup(ip.dest)) == NULLROUTE){
  198.         /* No route exists, return unreachable message */
  199.         icmp_output(&ip,bp,DEST_UNREACH,HOST_UNREACH,NULLICMP);
  200.         free_p(bp);
  201.         return -1;
  202.     }
  203.     /* Check for output forwarding and divert if necessary */
  204.     iface = rp->interface;
  205.     if(iface->forw != NULLIF)
  206.         iface = iface->forw;
  207.  
  208.     /* Find gateway; zero gateway in routing table means "send direct" */
  209.     if(rp->gateway == (int32)0)
  210.         gateway = ip.dest;
  211.     else
  212.         gateway = rp->gateway;
  213.  
  214.     if(strict && gateway != ip.dest){
  215.         /* Strict source routing requires a direct entry */
  216.         icmp_output(&ip,bp,DEST_UNREACH,ROUTE_FAIL,NULLICMP);
  217.         free_p(bp);
  218.         return -1;
  219.     }
  220.     precedence = PREC(ip.tos);
  221.     delay = ip.tos & DELAY;
  222.     throughput = ip.tos & THRUPUT;
  223.     reliability = ip.tos & RELIABILITY;
  224.  
  225.     if(ip.length <= iface->mtu){
  226.         /* Datagram smaller than interface MTU; put header
  227.          * back on and send normally
  228.          */
  229.         if((tbp = htonip(&ip,bp)) == NULLBUF){
  230.             free_p(bp);
  231.             return -1;
  232.         }
  233.         return (*iface->send)(tbp,iface,gateway,
  234.             precedence,delay,throughput,reliability);
  235.     }
  236.     /* Fragmentation needed */
  237.     if(ip.fl_offs & DF){
  238.         /* Don't Fragment set; return ICMP message and drop */
  239.         icmp_output(&ip,bp,DEST_UNREACH,FRAG_NEEDED,NULLICMP);
  240.         free_p(bp);
  241.         return -1;
  242.     }
  243.     /* Create fragments */
  244.     offset = (ip.fl_offs & F_OFFSET) << 3;
  245.     mf_flag = ip.fl_offs & MF;    /* Save original MF flag */
  246.     while(length != 0){        /* As long as there's data left */
  247.         int16 fragsize;        /* Size of this fragment's data */
  248.         struct mbuf *f_data;    /* Data portion of fragment */
  249.  
  250.         /* After the first fragment, should remove those
  251.          * options that aren't supposed to be copied on fragmentation
  252.          */
  253.         ip.fl_offs = offset >> 3;
  254.         if(length + ip_len <= iface->mtu){
  255.             /* Last fragment; send all that remains */
  256.             fragsize = length;
  257.             ip.fl_offs |= mf_flag;    /* Pass original MF flag */
  258.         } else {
  259.             /* More to come, so send multiple of 8 bytes */
  260.             fragsize = (iface->mtu - ip_len) & 0xfff8;
  261.             ip.fl_offs |= MF;
  262.         }
  263.         ip.length = fragsize + ip_len;
  264.  
  265.         /* Move the data fragment into a new, separate mbuf */
  266.         if((f_data = alloc_mbuf(fragsize)) == NULLBUF){
  267.             free_p(bp);
  268.             return -1;
  269.         }
  270.         f_data->cnt = pullup(&bp,f_data->data,fragsize);
  271.  
  272.         /* Put IP header back on */
  273.         if((tbp = htonip(&ip,f_data)) == NULLBUF){
  274.             free_p(f_data);
  275.             free_p(bp);
  276.             return -1;
  277.         }
  278.         /* and ship it out */
  279.         if((*iface->send)(tbp,iface,gateway,
  280.             precedence,delay,throughput,reliability) == -1)
  281.             return -1;
  282.  
  283.         offset += fragsize;
  284.         length -= fragsize;
  285.     }
  286.     return 0;
  287. }
  288.  
  289. struct rt_cache rt_cache;
  290.  
  291. /* Add an entry to the IP routing table. Returns 0 on success, -1 on failure */
  292. int
  293. rt_add(target,bits,gateway,metric,interface)
  294. int32 target;        /* Target IP address prefix */
  295. unsigned int bits;    /* Size of target address prefix in bits (0-32) */
  296. int32 gateway;
  297. int metric;
  298. struct interface *interface;
  299. {
  300.     struct route *rp,**hp,*rt_lookup();
  301.     int16 hash_ip(),i;
  302.     int32 mask;
  303.  
  304.     if(interface == NULLIF)
  305.         return -1;
  306.  
  307.     rt_cache.target = 0;    /* Flush cache */
  308.  
  309.     /* Zero bits refers to the default route */
  310.     if(bits == 0){
  311.         rp = &r_default;
  312.     } else {
  313.         if(bits > 32)
  314.             bits = 32;
  315.  
  316.         /* Mask off don't-care bits */
  317.         mask = 0xffffffff;
  318.         for(i=31;i >= bits;i--)
  319.             mask <<= 1;
  320.  
  321.         target &= mask;
  322.         /* Search appropriate chain for existing entry */
  323.         for(rp = routes[bits-1][hash_ip(target)];rp != NULLROUTE;rp = rp->next){
  324.             if(rp->target == target)
  325.                 break;
  326.         }
  327.     }
  328.     if(rp == NULLROUTE){
  329.         /* The target is not already in the table, so create a new
  330.          * entry and put it in.
  331.          */
  332.         if((rp = (struct route *)malloc(sizeof(struct route))) == NULLROUTE)
  333.             return -1;    /* No space */
  334.         /* Insert at head of table */
  335.         rp->prev = NULLROUTE;
  336.         hp = &routes[bits-1][hash_ip(target)];
  337.         rp->next = *hp;
  338.         if(rp->next != NULLROUTE)
  339.             rp->next->prev = rp;
  340.         *hp = rp;
  341.     }
  342.     rp->target = target;
  343.     rp->gateway = gateway;
  344.     rp->metric = metric;
  345.     rp->interface = interface;
  346.  
  347.     return 0;
  348. }
  349.  
  350. /* Remove an entry from the IP routing table. Returns 0 on success, -1
  351.  * if entry was not in table.
  352.  */
  353. int
  354. rt_drop(target,bits)
  355. int32 target;
  356. unsigned int bits;
  357. {
  358.     register struct route *rp;
  359.     struct route *rt_lookup();
  360.     unsigned int i;
  361.     int16 hash_ip();
  362.     int32 mask;
  363.  
  364.     rt_cache.target = 0;    /* Flush the cache */
  365.  
  366.     if(bits == 0){
  367.         /* Nail the default entry */
  368.         r_default.interface = NULLIF;
  369.         return 0;
  370.     }
  371.     if(bits > 32)
  372.         bits = 32;
  373.  
  374.     /* Mask off don't-care bits */
  375.     mask = 0xffffffff;
  376.     for(i=31;i >= bits;i--)
  377.         mask <<= 1;
  378.  
  379.     target &= mask;
  380.  
  381.     /* Search appropriate chain for existing entry */
  382.     for(rp = routes[bits-1][hash_ip(target)];rp != NULLROUTE;rp = rp->next){
  383.         if(rp->target == target)
  384.             break;
  385.     }
  386.     if(rp == NULLROUTE)
  387.         return -1;    /* Not in table */
  388.  
  389.     if(rp->next != NULLROUTE)
  390.         rp->next->prev = rp->prev;
  391.     if(rp->prev != NULLROUTE)
  392.         rp->prev->next = rp->next;
  393.     else
  394.         routes[bits-1][hash_ip(target)] = rp->next;
  395.  
  396.     free((char *)rp);
  397.     return 0;
  398. }
  399.  
  400. /* Compute hash function on IP address */
  401. static int16
  402. hash_ip(addr)
  403. register int32 addr;
  404. {
  405.     register int16 ret;
  406.  
  407.     ret = hiword(addr);
  408.     ret ^= loword(addr);
  409.     ret %= NROUTE;
  410.     return ret;
  411. }
  412. #ifndef    GWONLY
  413. /* Given an IP address, return the MTU of the local interface used to
  414.  * reach that destination. This is used by TCP to avoid local fragmentation
  415.  */
  416. int16
  417. ip_mtu(addr)
  418. int32 addr;
  419. {
  420.     register struct route *rp;
  421.     struct route *rt_lookup();
  422.     struct interface *iface;
  423.  
  424.     rp = rt_lookup(addr);
  425.     if(rp == NULLROUTE || rp->interface == NULLIF)
  426.         return 0;
  427.  
  428.     iface = rp->interface;
  429.     if(iface->forw != NULLIF)
  430.         return iface->forw->mtu;
  431.     else
  432.         return iface->mtu;
  433. }
  434. #endif
  435. /* Look up target in hash table, matching the entry having the largest number
  436.  * of leading bits in common. Return default route if not found;
  437.  * if default route not set, return NULLROUTE
  438.  */
  439. static struct route *
  440. rt_lookup(target)
  441. int32 target;
  442. {
  443.     register struct route *rp;
  444.     int16 hash_ip();
  445.     int bits;
  446.     int32 tsave;
  447.     int32 mask;
  448.  
  449.     if(target == rt_cache.target)
  450.         return rt_cache.route;
  451.  
  452.     tsave = target;
  453.  
  454.     mask = ~0;    /* All ones */
  455.     for(bits = 31;bits >= 0; bits--){
  456.         target &= mask;
  457.         for(rp = routes[bits][hash_ip(target)];rp != NULLROUTE;rp = rp->next){
  458.             if(rp->target == target){
  459.                 /* Stash in cache and return */
  460.                 rt_cache.target = tsave;
  461.                 rt_cache.route = rp;
  462.                 return rp;
  463.             }
  464.         }
  465.         mask <<= 1;
  466.     }
  467.     if(r_default.interface != NULLIF){
  468.         rt_cache.target = tsave;
  469.         rt_cache.route = &r_default;
  470.         return &r_default;
  471.     } else
  472.         return NULLROUTE;
  473. }
  474. /* Convert IP header in host format to network mbuf */
  475. struct mbuf *
  476. htonip(ip,data)
  477. struct ip *ip;
  478. struct mbuf *data;
  479. {
  480.     int16 hdr_len;
  481.     struct mbuf *bp;
  482.     register char *cp;
  483.     int16 checksum;
  484.  
  485.     hdr_len = IPLEN + ip->optlen;
  486.     if((bp = pushdown(data,hdr_len)) == NULLBUF){
  487.         free_p(data);
  488.         return NULLBUF;
  489.     }
  490.     cp = bp->data;
  491.     
  492.     *cp++ = (IPVERSION << 4) | (hdr_len >> 2);
  493.     *cp++ = ip->tos;
  494.     cp = put16(cp,ip->length);
  495.     cp = put16(cp,ip->id);
  496.     cp = put16(cp,ip->fl_offs);
  497.     *cp++ = ip->ttl;
  498.     *cp++ = ip->protocol;
  499.     cp = put16(cp,0);    /* Clear checksum */
  500.     cp = put32(cp,ip->source);
  501.     cp = put32(cp,ip->dest);
  502.     if(ip->optlen != 0)
  503.         memcpy(cp,ip->options,(int)ip->optlen);
  504.  
  505.     /* Compute checksum and insert into header */
  506.     checksum = cksum(NULLHEADER,bp,hdr_len);
  507.     put16(&bp->data[10],checksum);
  508.  
  509.     return bp;
  510. }
  511. /* Extract an IP header from mbuf */
  512. int
  513. ntohip(ip,bpp)
  514. struct ip *ip;
  515. struct mbuf **bpp;
  516. {
  517.     char v_ihl;
  518.     int16 ihl;
  519.  
  520.     v_ihl = pullchar(bpp);
  521.     ip->version = (v_ihl >> 4) & 0xf;
  522.     ip->tos = pullchar(bpp);
  523.     ip->length = pull16(bpp);
  524.     ip->id = pull16(bpp);
  525.     ip->fl_offs = pull16(bpp);
  526.     ip->ttl = pullchar(bpp);
  527.     ip->protocol = pullchar(bpp);
  528.     (void)pull16(bpp);    /* Toss checksum */
  529.     ip->source = pull32(bpp);
  530.     ip->dest = pull32(bpp);
  531.  
  532.     ihl = (v_ihl & 0xf) << 2;
  533.     if(ihl < IPLEN){
  534.         /* Bogus packet; header is too short */
  535.         return -1;
  536.     }
  537.     ip->optlen = ihl - IPLEN;
  538.     if(ip->optlen != 0)
  539.         pullup(bpp,ip->options,ip->optlen);
  540.  
  541.     return ip->optlen + IPLEN;
  542. }
  543. /* Perform end-around-carry adjustment */
  544. int16
  545. eac(sum)
  546. register int32 sum;    /* Carries in high order 16 bits */
  547. {
  548.     register int16 csum;
  549.  
  550.     while((csum = sum >> 16) != 0)
  551.         sum = csum + (sum & 0xffffL);
  552.     return (int16) (sum & 0xffffl);    /* Chops to 16 bits */
  553. }
  554. /* Checksum a mbuf chain, with optional pseudo-header */
  555. int16
  556. cksum(ph,m,len)
  557. struct pseudo_header *ph;
  558. register struct mbuf *m;
  559. int16 len;
  560. {
  561.     register unsigned int cnt, total;
  562.     register int32 sum, csum;
  563.     register char *up;
  564.     int16 csum1;
  565.     int swap = 0;
  566.     int16 lcsum();
  567.  
  568.     sum = 0l;
  569.  
  570.     /* Sum pseudo-header, if present */
  571.     if(ph != NULLHEADER){
  572.         sum = hiword(ph->source);
  573.         sum += loword(ph->source);
  574.         sum += hiword(ph->dest);
  575.         sum += loword(ph->dest);
  576.         sum += uchar(ph->protocol);
  577.         sum += ph->length;
  578.     }
  579.     /* Now do each mbuf on the chain */
  580.     for(total = 0; m != NULLBUF && total < len; m = m->next) {
  581.         cnt = min(m->cnt, len - total);
  582.         up = (char *)m->data;
  583.         csum = 0;
  584.  
  585.         if(((long)up) & 1){
  586.             /* Handle odd leading byte */
  587.             if(swap)
  588.                 csum = uchar(*up++);
  589.             else
  590.                 csum = (int16)(uchar(*up++) << 8);
  591.             cnt--;
  592.             swap = !swap;
  593.         }
  594.         if(cnt > 1){
  595.             /* Have the primitive checksumming routine do most of
  596.              * the work. At this point, up is guaranteed to be on
  597.              * a short boundary
  598.              */
  599.             csum1 = lcsum((unsigned short *)up, cnt >> 1);
  600.             if(swap)
  601.                 csum1 = (csum1 << 8) | (csum1 >> 8);
  602.             csum += csum1;
  603.         }
  604.         /* Handle odd trailing byte */
  605.         if(cnt & 1){
  606.             if(swap)
  607.                 csum += uchar(up[--cnt]);
  608.             else
  609.                 csum += (int16)(uchar(up[--cnt]) << 8);
  610.             swap = !swap;
  611.         }
  612.         sum += csum;
  613.         total += m->cnt;
  614.     }
  615.     /* Do final end-around carry, complement and return */
  616.     return ~eac(sum) & 0xffff;
  617. }
  618. /* Machine-independent, alignment insensitive network-to-host long conversion */
  619. static int32
  620. get32(cp)
  621. register char *cp;
  622. {
  623.     int32 rval;
  624.  
  625.     rval = uchar(*cp++);
  626.     rval <<= 8;
  627.     rval |= uchar(*cp++);
  628.     rval <<= 8;
  629.     rval |= uchar(*cp++);
  630.     rval <<= 8;
  631.     rval |= uchar(*cp);
  632.  
  633.     return rval;
  634. }
  635.